package code1.binary_tree;

/**
 * 原题链接：https://leetcode.cn/problems/balanced-binary-tree/
 */
public class P110 {

    //求子树的深度
    public int getDepth(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=getDepth(root.left);
        int right=getDepth(root.right);
        return Math.max(left,right)+1;
    }

    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        int leftDepth=getDepth(root.left);
        int rightDepth=getDepth(root.right);
        if(Math.abs(leftDepth-rightDepth)>1){
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }

    //获取子树的高度
    int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHegiht=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        if(leftHegiht==-1 || rightHeight==-1){
            return -1;
        }
        return Math.abs(leftHegiht-rightHeight)>1?-1:Math.max(rightHeight,leftHegiht)+1;      //-1表示已经不是平衡二叉树了
    }

    public boolean isBalanced2(TreeNode root) {
        int height = getHeight(root);
        if(height==-1){
            return false;
        }else{
            return true;
        }
    }
}
